package com.lw.leetcode.binary.a;

/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 *
 * @Author liw
 * @Date 2021/5/8 17:42
 * @Version 1.0
 */
public class Search2 {

    public static void main(String[] args) {
        Search2 search = new Search2();
        int[] nums = {4, 5};
        // [1,0,1,1,1]
        // [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1]
//        int[] nums = {1,0,1,1,1};
//        int[] nums = {2,3,4,5,6,7,1};
//        int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};

//        int aa = getStartIndex(nums);
//        System.out.println(aa);


        int search1 = search.search(nums, 6);
        System.out.println(search1);


    }

    public int search(int[] nums, int target) {
        if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
            return 0;
        }
        int min = getMin(nums, target);
        int max = getMax(nums, target);
        return max - min + 1;
    }

    private int getMin(int[] nums, int target) {
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (nums[m] < target) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return st;
    }

    private int getMax(int[] nums, int target) {
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] > target) {
                end = m - 1;
            } else {
                st = m;
            }
        }
        return st;
    }

}
